package solutions.leetcode.normal;

import solutions.lib.BaseSolution;

/**
 * @author lizhidong
 * <a href="https://leetcode-cn.com/problems/next-permutation/">31. 下一个排列</a>
 */
public class Solution31 extends BaseSolution {

    public void nextPermutation(int[] nums) {
        // 先从后边找，如果一直在增那就继续找
        int p = nums.length - 1;
        while (p > 0) {
            if (nums[p - 1] < nums[p]) {
                break;
            }
            p--;
        }
        if (p != 0) {
            // 如果有一个突然变小了
            int pivot = p - 1;
            p = nums.length - 1;
            while (p > pivot) {
                // 从后往前，找到第一个比 pivot 大的数，交换，剩余的翻转
                if (nums[p] > nums[pivot]) {
                    int t = nums[p];
                    nums[p] = nums[pivot];
                    nums[pivot] = t;
                    revert(nums, pivot + 1, nums.length - 1);
                    return;
                } else {
                    p --;
                }
            }
        } else {
            // 如果从后往前一直在递增，那已经是最大值
            revert(nums, 0, nums.length - 1);
        }
    }

    /**
     * 从 left 到 right 翻转
     */
    private void revert(int[] nums, int left, int right) {
        while (left < right) {
            int t = nums[left];
            nums[left] = nums[right];
            nums[right] = t;
            left++;
            right--;
        }
    }

    public static void main(String[] args) {
        Solution31 solution = new Solution31();
        int[] val = new int[] {
                1,3,2
        };
        solution.nextPermutation(val);
        printVals(val);
    }
}
